/**
 * [53] 最大子数组和
 * @format
 * @lc app=leetcode.cn id=53 lang=javascript
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number}
 */
// 动态规划
// 思路
// 1 和大于零的前提下保持连续，可能获得更大的和
// 2 记录下仅包含正数的连续和，最后与连续和比较
var maxSubArray = function (nums) {
    let [sumA, sumP, sumM] = [0, 0, 0]
    let [temp, max, flag] = [0, nums[0], false]
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] > max) max = nums[i]
        if (nums[i] >= 0) {
            flag = true
            sumA += nums[i]
            temp += nums[i]
            sumP = Math.max(sumP, temp)
        } else {
            sumA + nums[i] > 0 ? (sumA += nums[i]) : (sumA = 0)
            temp = 0
        }
        sumM = Math.max(sumM, sumA, sumP)
    }
    return flag ? sumM : max
}
// 提交结果：
// Accepted
// 210/210 cases passed (69 ms)
// Your runtime beats 92.1 % of javascript submissions
// Your memory usage beats 15.68 % of javascript submissions (58 MB)

// debugger
// const nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
// const MAX = maxSubArray(nums)
// console.log(MAX)
// @lc code=end
